import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mac
 * Date: 2022-09-25
 * Time: 16:27
 */
public class Day6 {
    //349.两个数组的交集 - 标记
    public int[] intersection1(int[] nums1, int[] nums2) {
        int[] array = new int[1001];
        int[] ret = new int[1001];
        int j = 0;
        for (int i = 0; i < nums1.length; i++) {
            array[nums1[i]] = 1;
        }
        j = 0;
        for (int i = 0; i < nums2.length; i++) {
            if (array[nums2[i]] == 1){
                ret[j] = nums2[i];
                j++;
                array[nums2[i]] = 0;
            }
        }
        return Arrays.copyOf(ret, j);
    }
    public int[] intersection2(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        //遍历数组1
        for (int i : nums1) {
            set1.add(i);
        }
        //遍历数组2的过程中判断哈希表中是否存在该元素
        for (int i : nums2) {
            if (set1.contains(i)) {
                resSet.add(i);
            }
        }
        int[] resArr = new int[resSet.size()];
        int index = 0;
        //将结果几何转为数组
        for (int i : resSet) {
            resArr[index++] = i;
        }
        return resArr;
    }

    //350.两个数组的交集II - 标记
    public int[] intersect(int[] nums1, int[] nums2) {
        int[] array = new int[1001];
        int[] ret = new int[1001];
        int j = 0;
        for (int i = 0; i < nums1.length; i++) {
            array[nums1[i]]++;
        }
        j = 0;
        for (int i = 0; i < nums2.length; i++) {
            if (array[nums2[i]] != 0){
                ret[j] = nums2[i];
                j++;
                array[nums2[i]]--;
            }
        }
        return Arrays.copyOf(ret, j);
    }

    //414.第三大的数 - 标记
    public int thirdMax1(int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        for (int i = nums.length - 1; i >= 1; i--) {
            if (nums[i] > nums[i - 1]){
                count++;
            }
            if (count == 2){
                return nums[i - 1];
            }
        }
        return nums[nums.length - 1];
    }
    public int thirdMax(int[] nums) {
        if (nums.length == 1){
            return nums[0];
        }
        if (nums.length == 2){
            return Math.max(nums[0], nums[1]);
        }
        int max1 = Integer.MIN_VALUE;
        int max2 = Integer.MIN_VALUE;
        int max3 = Integer.MIN_VALUE;
        boolean f = true;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == Integer.MIN_VALUE && f){
                count++;
                f = false;
            }
            if (nums[i] > max1){
                count++;
                max3 = max2;
                max2 = max1;
                max1 = nums[i];
            }else if (nums[i] > max2 && nums[i] < max1){
                count++;
                max3 = max2;
                max2 = nums[i];
            }else if (nums[i] > max3 && nums[i] < max2){
                count++;
                max3 = nums[i];
                count++;
            }
        }
        return count >= 3 ? max3 : max1;
    }

    //448.找到数组中所有消失的数字 - 标记
    public List<Integer> findDisappearedNumbers1(int[] nums) {
        List<Integer> list = new ArrayList<>();
        int[] array = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            array[nums[i]] = 1;
        }
        for (int i = 1; i <= nums.length; i++) {
            if (array[i] == 0){
                list.add(i);
            }
        }
        return list;
    }

    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> results = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[Math.abs(nums[i]) - 1] > 0) {
                nums[Math.abs(nums[i]) - 1] = - nums[Math.abs(nums[i]) - 1];
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                results.add(i + 1);
            }
        }
        return results;
    }

    //455.分发饼干 - 标记
    public int findContentChildren(int[] g, int[] s) {
        int child = 0;
        int cookie = 0;
        Arrays.sort(g);
        Arrays.sort(s);

        while (child < g.length && cookie < s.length){
            if (g[child] <= s[cookie]){
                child++;
            }
            cookie++;
        }
        return child;
    }

    //463.岛屿的周长
    public static int islandPerimeter(int[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1){
                    count += 4;
                }
                if (i > 0 && grid[i][j] == 1 && grid[i - 1][j] == 1){
                    count -= 2;
                }
                if (j > 0 && grid[i][j] == 1 && grid[i][j - 1] == 1) {
                    count -= 2;
                }
            }
        }
        return count;
    }
}
